#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

class Solution {
    typedef pair<int, int> PII;

public:
    vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {
        int m = mat.size(), n = mat[0].size();
        int dr[] = { -1, 1, 0, 0 }, dc[] = { 0, 0, -1, 1 };
        vector<vector<int>> ret(m, vector<int>(n, 0));
        vector<vector<bool>> vis(m, vector<bool>(n, false));
        queue<PII> q;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (mat[i][j] == 0) {
                    q.push({ i, j });
                    vis[i][j] = 1;
                }
            }
        }
        int distance = 0;
        while (!q.empty()) {
            int ct = q.size();
            distance++;
            while (ct--) {
                auto [r, c] = q.front();
                q.pop();
                for (int i = 0; i < 4; i++) {
                    int nr = r + dr[i], nc = c + dc[i];
                    if (nr >= 0 && nr < m && nc >= 0 && nc < n &&
                        !vis[nr][nc]) {
                        if (mat[nr][nc] == 1) {
                            ret[nr][nc] = distance;
                        }
                        q.push({ nr, nc });
                        vis[nr][nc] = 1;
                    }
                }
            }
        }
        return ret;
    }
};